<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      let arr = [1, 2, 4, 5, 6, 7, 8, 9, 22, 33, 44, 55];
      let arr1 = [1, 3, 5, 6];
      // //插入3
      // /*
      // 如果存在则返回所在位置,不存在则返回可以插入的位置
      // */
      Array.prototype.into = function (num) {
        if (this.indexOf(num) !== -1) {
          return this.indexOf(num);
        }
        //生命左右指针
        let left = 0;
        let right = this.length - 1;
        // for (var i = 0; i <= arr.length - 1; i++) {
        //   let center = Math.floor((right + left) / 2);

        //   //如果传入的值大于中间值则表示数字在数组的右边(升序)center=left,小于则在左边center=right
        //   num - arr[center] > 0 ? (left = center) : (right = center);
        //   //如果right-left的绝对值=1则表示找到最终位置返回center
        //   // console.log(right);
        //   if (right - left == 2) {
        //     return center;
        //   }
        // }
        // return i;
        // // for (let j = arr.length - 1; j >= i; j--) {
        // //   arr[j + 1] = arr[j];
        // // }
        // // arr[i] = num;
        // // return arr;
        while (left <= right) {
          let center = Math.floor((left + right) / 2);
          if (num == this[center]) {
            return center;
          } else if (num < this[center]) {
            right = center - 1;
          } else {
            left = center + 1;
          }
        }
        return left;
      };

      // console.log(arr.into(3));
      console.log(arr1.into(5));
      console.log(arr1.into(2));
      console.log(arr1.into(7));
      // 一个从小到大排好序的数组。现输入一个数，要求按原来的规律将它插入数组中

      // var arr = [2, 5, 8, 9];

      // function insert(a, n) {
      //   // 检测新数字要放入的位置
      //   for (var i = 0; i < a.length; i++) {
      //     if (n < a[i]) {
      //       break;
      //     }
      //   }
      //   // 将原数组中从要插入的位置到最后的数据，全部向后挪一位
      //   for (var j = arr.length - 1; j >= i; j--) {
      //     a[j + 1] = a[j];
      //   }
      //   // 直接将数据放在要插入的位置
      //   a[i] = n;
      //   return a;
      // }

      // var a = insert(arr, 4);
      // console.log(a);
    </script>
  </body>
</html>
